home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / snip0493.zip / LL_MSORT.C < prev    next >
C/C++ Source or Header  |  1993-04-05  |  2KB  |  76 lines
  1. /*
  2. ** Here's an example of how to sort a singly-linked list.  I think it
  3. ** can be modified to sort a doubly-linked list, but it would get a bit
  4. ** more complicated.  Note that this is a recursive method, but the
  5. ** recursion depth is limited to be proportional to the base 2 log of
  6. ** the length of the list, so it won't "run away" and blow the stack.
  7. */
  8.  
  9. /* linked list sort -- public domain by Ray Gardner  5/90 */
  10.  
  11. #include <stdio.h>              /* for NULL definition */
  12. #include <string.h>
  13.  
  14. typedef struct list_struct {
  15.    struct list_struct *next;
  16.    char *key;
  17.    /* other stuff */
  18.    } list;
  19.  
  20. /* returns < 0 if *p sorts lower than *q */
  21. int keycmp (list *p, list *q)
  22. {
  23.       return strcmp(p->key, q->key);
  24. }
  25.  
  26. /* merge 2 lists under dummy head item */
  27. list *lmerge (list *p, list *q)
  28. {
  29.       list *r, head;
  30.  
  31.       for ( r = &head; p && q; )
  32.       {
  33.             if ( keycmp(p, q) < 0 )
  34.             {
  35.                   r = r->next = p;
  36.                   p = p->next;
  37.             }
  38.             else
  39.             {
  40.                   r = r->next = q;
  41.                   q = q->next;
  42.             }
  43.       }
  44.       r->next = (p ? p : q);
  45.       return head.next;
  46. }
  47.  
  48. /* split list into 2 parts, sort each recursively, merge */
  49. list *lsort (list *p)
  50. {
  51.       list *q, *r;
  52.  
  53.       if ( p )
  54.       {
  55.             q = p;
  56.             for ( r = q->next; r && (r = r->next) != NULL; r = r->next )
  57.                   q = q->next;
  58.             r = q->next;
  59.             q->next = NULL;
  60.             if ( r )
  61.                   p = lmerge(lsort(r), lsort(p));
  62.       }
  63.       return p;
  64. }
  65.  
  66. main (void)
  67. {
  68.       list *listp;                 /* pointer to start of list */
  69.  
  70.       /* first build unsorted list, then */
  71.  
  72.       lsort(listp);
  73.  
  74.       return 0;
  75. }
  76.